#include <stdio.h>
#include <stdlib.h>


/*

	二叉查找树是满足以下条件的二叉树：
	
		1.左子树上的所有节点值均小于根节点值，
		
		2右子树上的所有节点值均不小于根节点值，
		
		3，左右子树也满足上述两个条件。

　　二叉查找树的插入过程如下：
	
		1.若当前的二叉查找树为空，则插入的元素为根节点，
		
		2.若插入的元素值小于根节点值，则将元素插入到左子树中，
		
		3.若插入的元素值不小于根节点值，则将元素插入到右子树中。

　　二叉查找树的删除，分三种情况进行处理：

	　　1.p为叶子节点，直接删除该节点，再修改其父节点的指针（注意分是根节点和不是根节点），如图a。

	　　2.p为单支节点（即只有左子树或右子树）。让p的子树与p的父亲节点相连，删除p即可；（注意分是根节点和不是根节点）；如图b。

	　　3.p的左子树和右子树均不空。找到p的后继y，因为y一定没有左子树，所以可以删除y，并让y的父亲节点成为y的右子树的父亲节点，并用y的值代替p的值；
		  或者方法二是找到p的前驱x，x一定没有右子树，所以可以删除x，并让x的父亲节点成为y的左子树的父亲节点。
 */


struct tree
{
  int val;
  struct tree * lchild;
  struct tree * rchild;
};

struct tree * bt = NULL;

/* 递归 */
struct tree * insert(struct tree * root, int x)
{
  struct tree * src;

  src = (struct tree *) malloc (sizeof(struct tree));
  src->val = x;
  src->lchild = NULL;
  src->rchild = NULL;

  if (root == NULL)
    root = src;
  else if (x < root->val)
    root->lchild = insert(root->lchild, x);
  else
    root->rchild = insert(root->rchild, x);

  return root;
}

void insert_bst(struct tree * tree, int x)
{
  struct tree * src;

  src = (struct tree *) malloc (sizeof(struct tree));
  src->val = x;
  src->lchild = NULL;
  src->rchild = NULL;
  if (tree == NULL) {
    bt = src;
    return ;
  }

  while (tree->lchild != src && tree->rchild != src) {
    if (x < tree->val) {
      if (tree->lchild)
	tree = tree->lchild;
      else
	tree->lchild = src;
    }
    else {
      if (tree->rchild)
	tree = tree->rchild;
      else
	tree->rchild = src;
    }
  }
}


#define false 0
#define true  1
struct tree * search_bst(struct tree * tree, int x)
{
  unsigned char  solve = false;
  
  while (tree && !solve) {
    if (x == tree->val)
      solve = true;
    else if (x < tree->val)
      tree = tree->lchild;
    else
      tree = tree->rchild;
  }

  if (tree == NULL)
    printf("not found %d.\n", x);
  else
    printf("found!\n");

  return tree;
}

unsigned char delete_bst(struct tree * tree, int x)
{
  unsigned char find = false;
  struct tree * des, * s, * t;

  tree = bt;
  while (tree && !find) {	// 寻找被删元素
    if (x == tree->val)		// 找到被删元素 
      find = true;
    else if (x < tree->val) {	//沿左子树找
      des = tree;
      tree = tree->lchild;
    }
    else {		//沿右子树找 
      des = tree;
      tree = tree->rchild;
    }
  }

  if (tree == NULL) {
    printf("not found %d.\n", x);
    return;
  }

  if (tree->lchild == NULL && tree->rchild == NULL) {	//tree为叶子节点
    if (tree == bt)	//tree为根节点
      bt = NULL;
    else if (des->lchild == tree) 
      des->lchild = NULL;
    else
      des->rchild = NULL;

    free(tree);
  }
  else if (tree->lchild == NULL || tree->rchild == NULL) {	//tree为单支子树
    if (tree == bt) {	// tree为根节点
      if (tree->lchild == NULL)
	bt = tree->rchild;
      else
	bt = tree->lchild;
    }
    else {
      if (des->lchild == tree && tree->lchild) //tree是des的左子树且tree有左子树
	des->lchild = tree->lchild;		// 将tree的左子树链接到des的左指针上 
      else if (des->lchild == tree && tree->rchild)
	des->lchild = tree->rchild;
      else if (des->rchild == tree && tree->lchild)
	des->rchild = tree->lchild;
      else
	des->rchild = tree->rchild;
    }
    
    free(tree);
  }
  else {	// tree的左右子树均不为空
    t = tree;
    s = tree->lchild;	//从tree的左子节点开始

    while (s->rchild) {	//找到tree的前驱，即tree左子树中值最大的节点
      t = s;
      s = s->rchild;
    }

    tree->val = s->val;	//把节点s的值赋给tree
    if (t == tree)
      tree->lchild = s->lchild;
    else
      t->rchild = s->lchild;

    free(s);
  }

  return find;
}

void display_tree(struct tree * tree)
{
  if (tree == NULL)
    return ;

  if (tree->lchild != NULL)
    display_tree(tree->lchild);

  printf(" %d ", tree->val);

  if (tree->rchild != NULL)
    display_tree(tree->rchild);
}

void main()
{
  int array[10] = {4, 1, 45, 78, 345, 23, 12, 3, 6, 21}; 
  int i;
  struct tree * tree;

  for (i = 0; i < 10; i++) 
    insert_bst(bt, array[i]);
  display_tree(bt);printf("\n");

  insert_bst(bt, 88);
  insert_bst(bt, 38);
  display_tree(bt);printf("\n");

  search_bst(bt, 88);

  delete_bst(bt, 88);
  display_tree(bt);printf("\n");
}
